package chapter02;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SolveNQueens51 {
    /**
     * 回溯法                                                             位运算
     * 有一个数组record record[i]表示i行的皇后在哪一列                      1.limit==(1<<n)-1 二进制从右到左1~n位全为1 其余为0
     * process(pos,path) 表示尝试第pos行的皇后,加入path                    2.colLim leftLim rightLim
     * 每一行皇后都可以尝试所有列col的位置 0~length-1                         列限制  左上对角线限制  右上对角线限制
     * pos行皇后在col列合法判断：不能与其他皇后同行 同列 对角线上               都是二进制表示 从右到左共n位 0可以放 1不可以放
     * 判断：当前皇后在pos行 col列                                         3.pos=limit&(~(colLim|leftLim|rightLim))
     *     row->[0,pos) 前pos-1行                                           表示成二进制位上有1就可以放
     *     col==record[row]||abs(pos-row)==abs(record[row]-col)          4.mostRightOne=pos&(-pos) 取出最右侧1
     *     都不符合                                                         pos=pos-mostRightOne 最右侧1上考虑过 变为0
     * 若当前pos行col列皇后位置合法 记录pos行皇后位置 record[pos]=col         posOne=Integer.bitCount(mostRightOne-1)+1;
     * 将pos行皇后加入路径path 尝试pos+1行皇后合法位置 process(pos+1,path)       二进制最右侧1从右到左在第几位上 就是皇后位置
     * 退出process(pos+1,path) 尝试pos行其他列的时候 应将上次加入path       5.根据皇后位置 组成字符串
     * 的皇后取出 以达到回溯效果                                           6.colLim|mostRightOne  把新增皇后位置加入列限制
     * 递归出口：                                                           (leftLim|mostRightOne)<<1 更新左上对角线限制
     *     pos==n 表示n行皇后都正确 将这条路径path加入列表中                  (rightLim|mostRightOne)>>>1 更新右上对角线限制
     *                                                                   递归出口：
     *                                                                       当colLim==limit 表明列限制已满 将path加入列表
     */
    List<List<String>> lists=new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        int[] record=new int[n];
        process(n,0,new ArrayList<>(),record);
        return lists;
    }

    public void process(int n,int pos,List<String> path,int[] record){
        if(pos==n){
            lists.add(new ArrayList<>(path));
        }
        for(int col=0;col<n;col++){
            if(isValid(pos,col,record)){
                StringBuffer strBuff=new StringBuffer();
                for(int i=0;i<col;i++){
                    strBuff.append(".");
                }
                strBuff.append("Q");
                for(int i=col+1;i<n;i++){
                    strBuff.append(".");
                }
                record[pos]=col;
                path.add(strBuff.toString());
                process(n,pos+1,path,record);
                path.remove(path.size()-1);
            }
        }
    }

    public boolean isValid(int pos,int col,int[] record){
        for(int i=0;i<pos;i++){
            if(col==record[i]||Math.abs(i-pos)==Math.abs(record[i]-col)){
                return false;
            }
        }
        return true;
    }

    //位
    public List<List<String>> solveNQueens1(int n) {
        process1(n,(1<<n)-1,0,0,0,new ArrayList<>());
        return lists;
    }

    public void process1(int n,int limit,int colLim,int leftLim,int rightLim,List<String> path){
        if(limit==colLim){
            lists.add(new ArrayList<>(path));
            return;
        }
        int pos=limit&(~(colLim|leftLim|rightLim));
        int mostRightOne=0;
        while (pos!=0){
            StringBuffer stringBuffer=new StringBuffer();
            mostRightOne=pos&(-pos);
            pos=pos-mostRightOne;
            int posOne=Integer.bitCount(mostRightOne-1);
            for(int i=1;i<=posOne;i++){
                stringBuffer.append('.');
            }
            stringBuffer.append('Q');
            for(int i=posOne+2;i<=n;i++){
                stringBuffer.append('.');
            }
            path.add(stringBuffer.toString());
            process1(n,limit,colLim|mostRightOne,(leftLim|mostRightOne)<<1,(rightLim|mostRightOne)>>>1,path);
            path.remove(path.size()-1);
        }
    }
}
